package com.dyz.leetcode._08_StackAndQueue;

import java.util.ArrayDeque;

public class _42_trap {
    //暴力解法
    public int trap(int[] height) {
        int ans = 0;
        for(int i=1; i<height.length-1; i++){
            //  求左边的最大值
            int leftHeight = 0;
            for(int j=i-1; j>=0;j--){
                leftHeight = Math.max(leftHeight, height[j]);
            }

            //求右边最大值
            int rightHeight = 0;
            for(int j=i+1; j<height.length; j++){
                rightHeight = Math.max(rightHeight, height[j]);
            }
            //当前这个柱子能装水的单位数min(leftHeight, rightHeight)-height[i]
            int maxHeight = Math.min(leftHeight, rightHeight);
            if(maxHeight>height[i]){
                ans+=maxHeight-height[i];
            }
        }
        return ans;
    }
    //双指针
    public int trap3(int[] height) {
        int n = height.length;
        if (n <= 2) {return 0;}

        int leftMax = 0, rightMax = 0;
        // 注意：left 必须从 0 开始，right 必须从 n - 1 开始
        // 原因：第一根柱子或者最后一根柱子有可能是最大值
        int left = 0, right = n - 1;
        int ans = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
    //单调栈
    public int trap2(int[] height) {
        int n = height.length;
        if (n <= 2) {return 0;}
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        for(int i=0; i<height.length; i++){
            while (!stack.isEmpty()&& height[i]>height[stack.peek()]){
                int preIndex = stack.peek();
                stack.pop();
                if(stack.isEmpty()){break;}
                int leftIndex = stack.peek();
                int curWight = i-leftIndex-1;
                int curHeight = Math.min(height[leftIndex], height[i])-height[preIndex];
                ans+=curHeight*curWight;
            }

            stack.push(i);

        }
        return ans;
    }
}
